package Sequence;

import java.util.ArrayList;
import java.util.List;

public class Test0216 {
    public static void main(String[] args) {
        new Solution0216_1().combinationSum3(3,7);
    }
}

class Solution0216_1 {
    int n,k;
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        this.n = n;
        this.k = k;

        backtrack(0,1,0,new Integer[k]);
        return ans;
    }

    public void backtrack(int row, int column,int sum,Integer[] record) {
        if (column<=9&&n-sum>=column){
            sum+=column;
            record[row]=column;

            if(row==k-1){
                if (sum==n){
                    ans.add(List.of(record));
                }
            } else{
                backtrack(row+1,column+1,sum,record);
            }

            sum-=column;
            if (column<9&&n-sum>=column+1){
                backtrack(row,column+1,sum,record);
            }
        }
    }
}
